package developer.算法.栈.每日温度;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author zhangyongkang
 * @time 2025/4/3 14:52
 * @description 代码
 * 提示
 * 给定一个整数数组 temperatures
 * ，表示每天的温度，返回一个数组 answer ，
 * 其中 answer[i] 是指对于第 i 天
 * 下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 * <p>
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 * <p>
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 */
public class EveryDayTemperature {
    public static void main(String[] args) {
        Solution5 solution = new Solution5();
        System.out.println(Arrays.toString(solution.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
        System.out.println(Arrays.toString(solution.dailyTemperatures(new int[]{30, 40, 50, 60})));
        System.out.println(Arrays.toString(solution.dailyTemperatures(new int[]{30, 60, 90})));
        System.out.println(Arrays.toString(solution.dailyTemperatures(new int[]{89, 62, 70, 58, 47, 47, 46, 76, 100, 70})));
        //[8, 1, 2, 2, 2, 2, 1, 1, 0, 0]
        //[8 ,1 ,5 ,4 ,3 ,2 ,1 ,1 ,0 ,0]

    }


    static class Solution5 {
        public int[] dailyTemperatures(int[] temperatures) {
            Stack<Integer> stack = new Stack<>();
            int[] res = new int[temperatures.length];
            for (int i = 0; i < temperatures.length; i++) {
                while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    //stack中是个有序的最小栈  5 3 2 1
                    //比自己小的值都弹出来
                    Integer pop = stack.pop();
                    res[pop] = i - pop;
                }
                stack.push(i);
            }
            return res;
        }
    }


    static class Solution4 {
        public int[] dailyTemperatures(int[] temperatures) {
            //温度高的在栈底 温度高的在栈顶 为什么呢 因为只需要找到第一个比你高的即可
            Stack<Integer> stack = new Stack<>();
            int[] result = new int[temperatures.length];

            for (int i = 0; i < temperatures.length; i++) {
                int temperature = temperatures[i];

                //找到第一个比他大的即可 不用找到最大的！！这种场景可以考虑单调栈
                while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {//温度低的已经被清理
                    Integer pop = stack.pop();//idx
                    result[pop] = i - pop;
                }
                stack.push(i);
            }
            return result;
        }
    }


    static class SolutionSelf3 {

        public int[] dailyTemperatures(int[] temperatures) {
            int[] result = new int[temperatures.length];
            Stack<Integer> stack = new Stack<>();


            for (int i = 0; i < temperatures.length; i++) {
                int temperature = temperatures[i];
                //栈中的数据根据从小到大排列  如果当前温度高度栈顶温度 那么对历史的数据进行赋值
                while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                    Integer historyIdx = stack.pop();
                    result[historyIdx] = i - historyIdx;
                }
                stack.push(i);
            }
            return result;
        }
    }

    /**
     * 学习官方的写法
     * 单调栈的思想 栈中的元素 温度低的在栈顶 温度高的在栈底
     * 栈中存储的是结果的索引
     */
    static class SolutionSelf {
        public int[] dailyTemperatures(int[] temperatures) {
            Stack<Integer> stack = new Stack<>();

            int[] result = new int[temperatures.length];
            for (int i = 0; i < temperatures.length; i++) {
                int currentVal = temperatures[i];
                while (!stack.isEmpty() && currentVal > temperatures[stack.peek()]) {
                    Integer idx = stack.pop();
                    result[idx] = i - idx;
                }
                stack.push(i);
            }

            return result;
        }
    }

    static class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            Stack<Integer> ts = new Stack<>();
            int[] result = new int[temperatures.length];

            for (int i = temperatures.length - 1; i >= 0; i--) {
                Stack<Integer> currentStack = new Stack<>();
                int currentVal = temperatures[i];

                int days = 0;
                boolean found = false;
                while (!ts.isEmpty()) {
                    Integer pop = ts.pop();
                    currentStack.add(pop);
                    days++;
                    if (pop > currentVal) {
                        found = true;
                        break;
                    }
                }
                int size = currentStack.size();
                for (int j = 0; j < size; j++) {
                    ts.push(currentStack.pop());
                }
                ts.push(currentVal);
                result[i] = found ? days : 0;
            }
            return result;
        }
    }

    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/daily-temperatures/solutions/283196/mei-ri-wen-du-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class SolutionOfficial {

        public int[] dailyTemperatures(int[] temperatures) {
            int length = temperatures.length;
            int[] ans = new int[length];
            Deque<Integer> stack = new LinkedList<>();
            for (int i = 0; i < length; i++) {
                int temperature = temperatures[i];
                while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                    int prevIndex = stack.pop();
                    ans[prevIndex] = i - prevIndex;
                }
                stack.push(i);
            }
            /*
            核心思想 拿出当前的值与历史的数据进行比较
             */
            return ans;
        }
    }


}
